global  uint128_div_v2_asm

BITS 64

SECTION .text  align=16

; ********** uint128_div_v2_asm function **********
; C/C++ prototype:
; extern "C" void uint128_t uint128_div_v2_asm(uint128_t n, uint128_t d);
; Input:   n, d,
; Output:  return n/d

; input parameter
; n:  RSI:RDI,  RDI: low64(n), RSI: high64(n)
; d:  RCX:rdx,  RDX: low64(d), RCX: high64(d)
; ***********************************************************

uint128_div_v2_asm :

%define N_HI rsi
%define N_LO rdi
%define D_HI r10
%define D_LO r11
%define T_LO  r9   ; tmp_low
%define R_CNT rcx  ; counter

    mov D_LO, rdx           ; save n to D_HI:D_LO
    mov D_HI, rcx

    mov rax, N_LO
    mov rdx, N_HI
    sub rax, D_LO
    sbb rdx, D_HI           ; rdx:rax = n-d

    jc  return_ZERO         ; if n<d goto return_ZERO

    or D_HI, D_HI
    jz D_HI_IS_0            ; d is "0y" form, do xx/0y or 0x/0y
    jmp   L_XX_DIV_YY_IMPL  ; n is "xx" form and d is "yy" form, do xx / yy

D_HI_IS_0:                  ; d is "0y" form
    or D_LO,D_LO
    jz DIV_OVERFLOW         ; D_HI==0 and D_LO==0,

    cmp N_HI, D_LO
    jae L_XX_DIV_0Y_CASE2   ; n is "0x" form and d is "0y" form, do 0x/0y

L_XX_DIV_0Y_CASE1:          ; case 0x/0y or xx/0y, d<2^64, n/d<2^64
   mov rdx, N_HI
   mov rax, N_LO
   div D_LO
   xor rdx,rdx
   ret

L_XX_DIV_0Y_CASE2:          ; case xx/0y, n>2^64 and d<2^64, n/d>=2^64
%define R_Q1  r8
   xor rdx,rdx
   mov rax,N_HI
   div D_LO
   mov R_Q1,rax             ; n/d => R_Q1
   mov rax,N_LO
   div D_LO
   mov rdx,R_Q1             ; rdx:rax = n/d
   ret

;-----------------------------------------
; *** case 1:  n < d , return 0 **
return_ZERO:
    xor rdx,rdx
    xor rax,rax
    ret

;-----------------------------------------
; *** case 2:  n/0
DIV_OVERFLOW:   ; do 1/0
    mov rax, 1
    div D_LO
    ret

;-----------------------------------------
return_1:
    xor rdx,rdx
    mov rax, 1
    ret

;-----------------------------------------
; *********  case 3:  xx/yy form *********
L_XX_DIV_YY_IMPL:
%define R_Q   r8
    bsr	R_CNT, D_HI   ; bit counter of N_HI
    xor R_CNT,63      ; R_CNT= 63-R_CNT, lead zero counter of D_HI
    jz  return_1      ; D_HI>=2^63, return 1

    shld D_HI, D_LO, cl
    shl  D_LO, cl       ; "D_HI:D_LO"=(d*2^R_CNT)

    xor rdx, rdx
    mov rax, N_HI
    mov T_LO, N_LO
    shld rdx, rax,  cl
    shld rax, T_LO, cl
    shl  T_LO, cl       ; "rdx:rax:T_LO" = n*2^cnt

    div  D_HI           ; q= (n*2^CNT)/(d*2^cnt)
    mov  R_Q,   rax
    mov  R_CNT, rdx
    mul  D_LO           ; rdx:rax= q * D_LO
    sub  T_LO, rax
    sbb  R_CNT,rdx
    sbb  R_Q,  0

    xor  rdx,rdx
    mov  rax,R_Q
    ret
